#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int data_Type;
// 队列类型 结构体
typedef struct Node
{
    data_Type data;    // 数据域
    struct Node *next; // 指针域
} Node, *pNode;
typedef struct LinkQueue
{
    pNode front; // 队头
    pNode rear;  // 队尾
} LinkQueue;

LinkQueue *init_LinkQueue();                           // 初始化
int push_LinkQueue(LinkQueue *queue, data_Type value); // 入队
int pop_LinkQueue(LinkQueue *queue, data_Type *value); // 出队
int empty_LinkQueue(LinkQueue *queue);                 // 判空
data_Type front_LinkQueue(LinkQueue *queue);           // 取队头元素
data_Type back_LinkQueue(LinkQueue *queue);            // 取队尾元素
void clear_LinkQueue(LinkQueue *queue);                // 清空
void output_LinkQueue(LinkQueue *queue);               // 输出
int size_LinkQueue(LinkQueue *queue);                  // 大小
void destory_LinkQueue(LinkQueue **queue);             // 销毁
int main(int argc, char const *argv[])
{
    // 初始化
    LinkQueue *lkq = init_LinkQueue();
    // 入队
    printf("入队1 2 3 4\n");
    if (!push_LinkQueue(lkq, 1));
    else
        printf("push error\n");
    if (!push_LinkQueue(lkq, 2));
    else
        printf("push error\n");
    if (!push_LinkQueue(lkq, 3));
    else
        printf("push error\n");
    if (!push_LinkQueue(lkq, 4));
    else
        printf("push error\n");
    //
    printf("队头元素值：%d\t队尾元素值：%d\n", front_LinkQueue(lkq), back_LinkQueue(lkq));
    // 出队
    data_Type dat;
    if (!pop_LinkQueue(lkq, &dat))
        printf("出队：%d\n", dat);
    else
        printf("pup error\n");
    if (!pop_LinkQueue(lkq, &dat))
        printf("出队：%d\n", dat);
    else
        printf("pup error\n");
    // 再次入队
    printf("再次入队 100  200");
    if (!push_LinkQueue(lkq, 100))
        ;
    else
        printf("push error\n");
    if (!push_LinkQueue(lkq, 200))
        ;
    else
        printf("push error\n");
    // 输出
    output_LinkQueue(lkq);
    // 清空
    // clear_LinkQueue(lkq);

    // 长度
    int len = size_LinkQueue(lkq);
    printf("size:%d\n", len);
    // 再次出队
    if (!pop_LinkQueue(lkq, &dat))
        printf("出队：%d\n", dat);
    else
        printf("pup error\n");
    if (!pop_LinkQueue(lkq, &dat))
        printf("出队：%d\n", dat);
    else
        printf("pup error\n");
    if (!pop_LinkQueue(lkq, &dat))
        printf("出队：%d\n", dat);
    else
        printf("pup error\n");
    if (!pop_LinkQueue(lkq, &dat))
        printf("出队：%d\n", dat);
    else
        printf("pup error\n");

    // 销毁
    destory_LinkQueue(&lkq);
    printf("销毁后入队测试：\n");
    if (!push_LinkQueue(lkq, 1))
        ;
    else
        printf("push error\n");

    return 0;
}
// 初始化
LinkQueue *init_LinkQueue()
{
    LinkQueue *lkqueue = (LinkQueue *)malloc(sizeof(LinkQueue)); // 为了存储 对头和队尾指针 去分配一段空间
    if (lkqueue == NULL)
    {
        printf("malloc faild\n");
        return NULL;
    }
    // 由于前面还只是给两个指针  创建了一个空间  那实际头结点 还没有  也就是这两个指针还没有指向
    pNode head = (pNode)malloc(sizeof(Node));
    if (head == NULL)
    {
        // 释放原来为两个指针开辟的空间
        free(lkqueue);
        //
        printf("malloc faild2\n");
        return NULL;
    }
    // 头结点  不存放数据
    head->data = -1; // 这个数据随便给
    // 是一个空队列
    lkqueue->front = lkqueue->rear = head;

    // 头结点的next为空
    lkqueue->front->next = NULL;
    return lkqueue;
}
// 入队
int push_LinkQueue(LinkQueue *queue, data_Type value)
{
    if (queue == NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if (queue->front == NULL)
    {
        printf("stack is null\n");
        return -1;
    }
    if (queue->rear == NULL)
    {
        printf("stack is null2\n");
        return -1;
    }
    // 创建一个结点
    pNode newnode = (pNode)malloc(sizeof(Node)); //
    if (newnode == NULL)
    {
        printf("newmnode malloc faild\n");
        return -1;
    }
    // 更新数据
    newnode->data = value;
    newnode->next = NULL;
    // 修改指针
    queue->rear->next = newnode; // 将新节点插在后面
    queue->rear = newnode;       // 更新尾部指针
    return 0;
}
// 出队
int pop_LinkQueue(LinkQueue *queue, data_Type *value)
{
    if (queue == NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if (queue->front == NULL)
    {
        printf("queue is null\n");
        return -1;
    }
    if (queue->rear == NULL)
    {
        printf("queue is null2\n");
        return -1;
    }
    if (queue->front == queue->rear)
    {
        printf("queue is empty\n");
        return -1;
    }
    // 先保存要出去的数据的结点  因为后续要释放
    pNode t = queue->front->next; // 保存第一个结点
    queue->front->next = t->next; // 更新新的结点
    // 如果现在t是唯一的一个数据 t就是队尾  队尾指针将会变成一个野指针  如果出队当前这个元素，队列应该为空队列
    if (t == queue->rear)
    {
        queue->rear = queue->front; // 重新指向头结点
    }

    *value = t->data; // 将值取出
    free(t);          // 释放
    return 0;
}
// 判空
int empty_LinkQueue(LinkQueue *queue)
{
    return queue->rear == queue->front;
}
// 取队头元素
data_Type front_LinkQueue(LinkQueue *queue)
{
    if (queue == NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if (queue->front == NULL)
    {
        printf("queue is null\n");
        return -1;
    }
    if (queue->rear == NULL)
    {
        printf("queue is null2\n");
        return -1;
    }
    if (queue->front == queue->rear) // 空队  指向头结点
    {
        printf("queue is empty\n");
        return -1;
    }

    return queue->front->next->data; // 因为queue->front指向的是头结点  头结点是部分存放数据的
}
// 取队尾元素
data_Type back_LinkQueue(LinkQueue *queue)
{
    if (queue == NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if (queue->front == NULL)
    {
        printf("queue is null\n");
        return -1;
    }
    if (queue->rear == NULL)
    {
        printf("queue is null2\n");
        return -1;
    }
    if (queue->front == queue->rear) // 空队  指向头结点
    {
        printf("queue is empty\n");
        return -1;
    }
    return queue->rear->data; // queue->rear指向的就是队尾元素
}
// 清空  清空队列中的数据结点
void clear_LinkQueue(LinkQueue *queue)
{
    if (queue == NULL)
    {
        printf("queue is error\n");
        return;
    }
    if (queue->front == NULL)
    {
        printf("stack is null\n");
        return;
    }
    if (queue->rear == NULL)
    {
        printf("stack is null2\n");
        return;
    }
    if (empty_LinkQueue(queue))
    {
        return;
    }
    pNode t = queue->front->next; // 从头结点的第一个数据元素开始删除 队头
    while (t != NULL)
    {
        // 更新新的队头
        queue->front->next = t->next;
        printf("clear data:%d\n", t->data);
        free(t);
        t = queue->front->next;
    }
    // 将队头和队尾 同时指向  head
    queue->rear = queue->front;
}
// 输出
void output_LinkQueue(LinkQueue *queue)
{
    if (queue == NULL)
    {
        printf("queue is error\n");
        return;
    }
    if (queue->front == NULL)
    {
        printf("stack is null\n");
        return;
    }
    if (queue->rear == NULL)
    {
        printf("stack is null2\n");
        return;
    }
    if (empty_LinkQueue(queue))
    {
        return;
    }
    pNode t = queue->front->next; // 从头结点的第一个数据元素开始删除 队头
    while (t != NULL)
    {
        printf("%d ", t->data);
        t = t->next;
    }
    printf("\n");
}
// 大小
int size_LinkQueue(LinkQueue *queue)
{
    if (queue == NULL)
    {
        printf("queue is error\n");
        return -1;
    }
    if (queue->front == NULL)
    {
        printf("stack is null\n");
        return -1;
    }
    if (queue->rear == NULL)
    {
        printf("stack is null2\n");
        return -1;
    }
    if (empty_LinkQueue(queue))
    {
        return 0;
    }
    int i = 0;
    pNode t = queue->front->next; // 从头结点的第一个数据元素开始删除 队头
    while (t != NULL)
    {
        i++;
        t = t->next;
    }
    return i;
}
// 销毁
void destory_LinkQueue(LinkQueue **queue)
{
    if ((*queue) == NULL)
    {
        printf("queue is error\n");
        return;
    }
    if ((*queue)->front == NULL)
    {
        printf("queue is null\n");
        return;
    }
    if ((*queue)->rear == NULL)
    {
        printf("queue is null2\n");
        return;
    }
    clear_LinkQueue(*queue); // 先清空

    free((*queue)->front); // 就是queue->rear  就是释放头结点
    /*
    分配一个头节点（head）
    其内存是通过 malloc(sizeof(Node)) 分配的
    头节点是队列的基础框架，用于维护队列的起点
    */

    free(*queue); // 释放结构体
    /*
    LinkQueue 结构体本身是通过 malloc(sizeof(LinkQueue)) 分配的
    它包含两个指针（front 和 rear）
    但不直接存储数据*/

    *queue = NULL;
}